package com.jake.data_structure_learning.graph1;

import java.util.ArrayList;
import java.util.List;

/**
 * copyright (C), 2021, 北京同创永益科技发展有限公司
 *
 * @author WangXiang
 * @version 1.0.0
 * @create 2021/4/9 16:39
 * @description <author>                <time>                  <version>
 * WangKai                2021/4/9 16:39          1.0.0
 */
public abstract class Graph {
    // 顶点
    private int V;

    // 边
    private int E;

    // 邻接表
    private List[] adj;

    // 构造一个含有V个顶点的图，但是不含边
    Graph(int V) {
        adj = new ArrayList[V];
        for (int i = 0; i < V; i++) {
            adj[i] = new ArrayList<Integer>();
        }
        this.V = V;
    }

    /**
     * @return 返回顶点的数量
     */
    int V() {
        return V;
    }

    /**
     * @return 返回边的数量
     */
    int E() {
        return E;
    }

    /**
     * 在图中添加一条边v-w
     *
     * @param v
     * @param w
     */
    abstract void addEdge(int v, int w);

    /**
     * 获得与v相邻的所有顶点
     *
     * @param v
     * @return
     */
    abstract List<Integer> adj(int v);

    /**
     * 与结点s相连通的所有结点
     *
     * @param s
     * @return
     */
    abstract List<Integer> search(int s);

    /**
     * 是否存在S结点到V结点的路径
     *
     * @param s
     * @param v
     * @return
     */
    abstract boolean hasPathTo(int s, int v);

    /**
     * 找出s到v结点的路径
     *
     * @param s
     * @param v
     * @return
     */
    abstract List<Integer> pathTo(int s, int v);


    /**
     * 便于进行打印
     *
     * @return
     */
    @Override
    public String toString() {
        String s = "Graph{" +
                "V=" + V +
                ", E=" + E +
                '}';
        for (int v = 0; v < V; v++) {
            s += (v + ":");
            for (int w : this.adj(v)) {
                s += w + " ";
            }
            s += "\n";
        }
        return s;
    }
}
